package KnapsackGreedy;

/**
 * 作者:TC
 * 时间:应用贪婪技术求解背包问题 21:59
 * 描述:没有bug
 */
import java.util.Scanner;
public class knapsackGreedy {
    public static void main(String[] args) {
        Scanner Sc = new Scanner(System.in);
        System.out.println("请输入物品个数N：");
        int N= Sc.nextInt();
        System.out.println("请输入背包容量ww：");
        float ww = Sc.nextFloat();
        float[] w = new float[N];		//物品重量
        float[] v = new float[N];		//物品价值
        System.out.println("请输入物品的重量和价值使用空格隔开");
        for (int i = 0; i < N; i++) {
            // 接下来有 N 行，每行有两个整数:v[i],w[i]，用空格隔开，分别表示第i件物品的体积和价值
            w[i] = Sc.nextInt();
            v[i] = Sc.nextInt();
        }
        System.out.println("物品重量为：");
        for(int j=0;j<N;j++){
            System.out.print(w[j]+" ");
        }
        System.out.println("");
        System.out.println("物品价值为：");
        for(int j=0;j<N;j++){
            System.out.print(v[j]+" ");
        }
        System.out.println("");
        float[] x = new float[N];		//问题的解
        //创建一个实列对象调用类中的方法sort
        knapsackGreedy p = new knapsackGreedy();
        //对于单位重量的价值进行排序
        System.out.println("排序后的物品重量以及价值为：");
        p.Sort(N, v, w);
        float s = p.knapsack(w, v, x, ww, N);
        System.out.println("最优解的最终价值为："+s);
    }
    //依次放入最大单位价值的物品求最优解
    float knapsack(float w[], float v[], float x[], float ww, int N) {
        float total = 0;
        int i = 0;

        for (i = 0; i < N; i++) {
            x[i] = 0;
        }

        i = 0; // 重置 i 的值

        while (i < N && w[i] <= ww) { // 条件为 i < N && w[i] <= ww
            x[i] = 1;
            total = total + v[i];
            ww = ww - w[i];
            i++;
        }
        if (i < N) {//当w[i]>ww时,求解拆分物品i单位重量价值后，求解total的值，最后将x[i]置1为装入标记
           x[i] = ww / w[i];
           total = total + x[i] * v[i];
           //x[i]置空1
           x[i]=1;
        }
        System.out.println("装入背包的物品为按照单位重量排序后的物品：");
        for (int j = 0; j < N; j++) {
            if (x[j] == 1) {
                System.out.print((j+1)+ " ");
            }
        }
        System.out.println("");
        return total;
    }
    //使用冒泡排序算法进行排序
    private void Sort(int N, float v[], float w[]) {
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - i - 1; j++) {
                if (v[j] / w[j] < v[j + 1] / w[j + 1]) {
                    float tempV = v[j];
                    v[j] = v[j + 1];
                    v[j + 1] = tempV;
                    float tempW = w[j];
                    w[j] = w[j + 1];
                    w[j + 1] = tempW;
                }
            }
        }
        for(int a=0;a<N;a++){
            System.out.println(w[a]+ " "+v[a]);
        }
    }

}